1316. Одинаковые шары

Корабельная роща. 1898. При сравнении колорита «Корабельной рощи», позднего произведения Шишкина, с колоритом ранних его работ, ясно видно, что художник-пейзажист, подобно своим современникам-жанристам, перешел от локального понимания цвета к скупой, но целостной цветовой гамме. В основе этой гаммы лежит передача объединяющей изображение светотени.

В этой картине Шишкин нашел в цветовом объединении серовато-коричневых стволов елей и зелени мха на первом плане новое для себя тональное понимание цвета.

Картина интересна также новым способом передачи пространства леса. Деревья изображаются не целиком, а как бы срезаются рамой. Ели даются видимыми в непосредственной близости, но когда зритель смотрит на них, он не способен охватить всю картину в целом.

В непрозрачной закрытой урне с небольшим отверстием в крышке находится n шаров (n четно), ровно половина из которых черные, остальные – белые. У Вас есть симметрическая монета, которую Вы начинаете подбрасывать. Если выпадет орел, то Вы извлекаете белый шар, если решка – то черный. Когда в урне остается в точности два шара, то они оказываются одинакового цвета и смысла дальше бросать монету нет (до этого момента в урне обязательно присутствуют хотя бы один белый и хотя бы один черный шар). Какая вероятность того, что произойдет описанная ситуация?

Вход. Каждая строка является отдельным тестом и содержит количество шаров в урне n (0 < n £ 10⁵, n четно).

Выход. Для каждого теста в отдельной строке вывести вероятность того, что произойдет описанная в условии задачи ситуация. Вероятность следует выводить с 8 десятичными знаками.

Пример входа	Пример выхода
6 10 256	0.62500000 0.72656250 0.94998552

РЕШЕНИЕ

теория вероятности

Анализ алгоритма

Вычислим вероятность противоположного события X – того, что последними будут вынуты шары разного цвета. Для этого среди первых n – 2 вынутых шаров ровно половина должна быть белыми, половина – черными.

Рассмотрим схему испытаний Бернулли, где вероятность успеха (например, появления белого шара) равна p = 1/2, а неуспеха q = 1 – p = 1/2. Вероятность того, что среди n – 2 вынутых шаров будет ровно (n – 2) / 2 белых, равна

P(X) = =

Остается для каждого входного n вычислить значение P(X) и вывести 1 – P(X).

Хотя P(X) лежит в промежутке от 0 до 1 включительно, возможны проблемы с его непосредственным вычислением. Прологарифмируем равенство:

ln P(X) = ln(n – 2)! – –

После вычисления правой части равенства, возведем е в него, получив P(X). Логарифм факториала вычислим как сумму логарифмов:

ln n! = ln 1 + ln 2 + ln 3 + … + ln n

В связи с многократным входом, все ответы следует предвычислить и занести в массив.

Пример

Для n = 6 вероятность того, что последними будут вынуты шары разного цвета, равна

= =

Вероятность того, что последними будут вынуты шары одного цвета, равна 1 – = = 0,625.

Реализация алгоритма

Объявим необходимые массивы. В ячейке ans[i] будем запоминать значение .

#define MAX 100001

double lf[MAX], ans[MAX];

Занесем в lf[i] значение ln i!.

res = lf[1] = 0.0;

for(res = 0, i = 2; i < MAX; i++)

{

res += log((double)i);

lf[i] = res;

}

for(i = 2; i < MAX; i += 2)

{

res = lf[i/2-1];

res = lf[i-2] - (i-2)*log(2.0) – res - res;

Переменнмая res содержит ln. Заносим в ans[i] значение .

ans[i] = exp(res);

}

Для каждого входного значения n выводим ответ.

while(scanf("%d",&n) == 1)

printf("%.8lf\n",1 - ans[n]);